# 括号匹配算法:
#     parChecker为单一类型括号匹配
#     moreParChecker为三种括号匹配
import os, sys

# 把包的父目录添加到系统搜索路径
BASE_DIR=os.path.dirname(os.path.dirname(os.path.abspath(__file__)))
sys.path.append(BASE_DIR)

from base_data_structures.stack import Stack

# 简单圆括号匹配算法
def parChecker(symbolString):
    s = Stack()
    index = 0
    match = True

    while index < len(symbolString) and match:
        if symbolString[index] == '(':
            # 读入字符为左括号就压栈
            s.push(symbolString[index])
            
        else:
            # 读入字符为右括号时:         
            if s.isEmpty():
                # 首先判断栈是否为空,为空就表示不匹配
                match = False
            else:
                # 弹出左括号
                s.pop()
        index += 1
    
    if match and s.isEmpty():
        return True
    else:
        return False

# 大括号, 方括号, 圆括号匹配算法
def moreParChecker(symbolString):
    s = Stack()

    index =0 
    match = True
    while index < len(symbolString) and match:
        symbol=symbolString[index]
        if symbol in '{[(':
            s.push(symbol)
        else:
            if s.isEmpty():
                match=False
            else:
                top = s.pop()
                if not matches(top, symbol):
                    match=False
        index += 1
    if match and s.isEmpty():
        return True
    else:
        return False
def matches(open, close):
    opens = '([{'
    closes = ')]}'
    return opens.index(open)==closes.index(close)

print(moreParChecker('{[()]}'))

